#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// 2781. 最长合法子字符串的长度
// https://leetcode.cn/problems/length-of-the-longest-valid-substring/

class Solution
{
public:
    int longestValidSubstring(string word, vector<string> &forbidden)
    {
        unordered_set<string> recordStr;
        int minSize = INT32_MAX;
        int maxSize = 0;
        for (auto &s : forbidden)
        {
            minSize = min(minSize, (int)s.size());
            maxSize = max(maxSize, (int)s.size());
            recordStr.insert(s);
        }
        int ans = 0;
        int left = 0;
        for (int i = 0; i < word.size(); i++)
        {
            if (i - left + 1 == minSize)
            {
                if (recordStr.find(word.substr(left, minSize)) != recordStr.end())
                {
                    left++;
                }
            }
            if (i - left + 1 > minSize)
            {
                int size = minSize;
                for (int k = i - minSize + 1; k >= left && i - k + 1 <= maxSize; --k)
                {
                    string temp = word.substr(k, size++);
                    if (recordStr.find(temp) != recordStr.end())
                    {
                        left = k + 1;
                        break;
                    }
                }
            }
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};
int main()
{
    return 0;
}